// 递归快排
#include <stdio.h>
#include <stdlib.h>
void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}
// 重点是分析一次快排结束后 i和j的位置

void sort(int a[], int low, int high)
{
    if (low < high)
    {
        int i, j, prim;
        // 主元的选取这里是选取的low
        prim = low;
        // prim=pivot(a,low,high) 选取 low ,high,mid的中值
        swap(a[prim], a[low]);
        i = low + 1, j = high;
        while (1)
        {
            while (a[i] < a[prim])
            {
                i++;
            }
            while (a[j] > a[prim])
            {
                j--;
            }
            if (i < j)
                swap(a[i], a[j]);
            else
                break;
        }
        swap(a[j], a[low]);
        // 结束时 i处于主元右边一个元素 左边应该是low~i-2 右边应该是i~high
        // j则是处于主元位置 所以为了简便 这里使用j最好
        sort(a, low, i - 1);
        sort(a, j + 1, high);
    }
}
void quick_sort(int a[], int n)
{
    sort(a, 0, n - 1);
}

int main()
{
    /*******************code*******************/
    int a[] = {4, 3, 10, 8, 14, 13, 7, 30, 26, 17};
    quick_sort(a, 10);
    printf("quick_sort\n");
    for (int i = 0; i < 10; i++)
        printf("%3d", a[i]);
    printf("\n");
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
